\input basic
\parskip 12 pt
\parindent 0 pt
\magnify {1100}
\ctrline{\bf CS154 PROBLEM SET 4, SOLUTIONS}
3.21

Construct the DFA accepting the complement of the set using the construction
described in theorem 3.2.  Then apply the decision procedures to test for
emptiness and for infiniteness that are given in section 3.3.

3.25

We may remove states $e$, $f$, $g$, and $h$, since they can never be
reached.  I claim that the rest of the states are inequivalent.  State $d$
is different from the other states because it is the only accepting state.
State $c$ is distinguished from states $a$ and $b$ by the string $0$, which
takes $c$ to an accepting state, but takes the other states to non-accepting
states.  States $a$ and $b$ are distinguished from each other now by $1$,
which takes $a$ to $c$ and takes $b$ to $a$, since we already know that states
$a$ and $c$ are distinguishable.  (Alternatively, I could just say that
$a$ and $b$ are distinguished by the string $10$.)

Thus, the minimum-state automaton equivalent to the given DFA can be represented
by the left half of the diagram given with this problem.

3.26

(a) One equivalence class is the set of all strings with a $1$ preceding a $0$,
or with more $1$s than $0$s.
The other equivalence classes are of the form
$$\{{0}↑{m}{1}↑{n} | m-n=i\},$$
for all non-negative $i$.

(b) Since there are infinitely many equivalence classes, the language is not
regular.

(c) The equivalence classes are of the form
$$\{z | z \hbox{\rm\ the number of one's minus the number of zeroes in $z$ is $i$}\},$$
for all integral $i$.

3.28

I haven't solved this one yet.

I.

(a) The gsm is attached.  It rejects any program not of the form
$$program\ foo;\ var\ y:\ real;\ begin\ y:={(}↑{n}0.0{)}↑{n};end.$$
For any such program it outputs the string ${a}↑{n}{b}↑{n}$.

(b) The set of all Pascal programs is not regular.

II.

(a) A regular expression is empty if it is
\parskip 0 pt\parindent 1 truein \par
(i) $\{\}$, \par
(ii) the union of two empty regular expressions, \par
or (iii) the concatenation of an empty regular expression and anything else.
\parskip 12 pt\parindent 0 pt

(b) Define class (1) as all regular corresponding to $\{\}$, class (2)
as all regular expressions correspondning to $\epsilon$, class (2) as
all regular expressions corresponding to infinite sets, and class (4)
as all other regular expressions.

Then a regular expression is in class (1) if it is $\{\}$, the union of
two regular expressions in class (1), or the concatenation of a regular
expression in class (1) with a regular expression in any of the classes.
A regular expression is in class (2) if it is $\epsilon$, the union
of a regular expression in class (2) with a regular expression in class (1)
or (2), the concatenation of two regular expressions in class (2), or
the Kleene closure of a regular expression in class (1) or (2).  A regular
expression is in class (3) if it is the union of a regular expression in
class (3) with a regular expression in any class, the concatenation of
a regular expression in class (3) with a regular expression in class
(2) (3), or (4), or the Kleene closure of a regular expression in class
(3) or (4).  A regular expression is in class (4) if it is a symbol from
the alphabet, the union of a regular expression in class (4) with a regular
expression in class (1), (2), or (4), or the concatenation of a regular
expression in class (4) with a regular expression in class (2) or (4).

III.

I'll let you all think about this one a little longer.  The solution may
appear when you least expect it.

\vfill\eject\end